#include <assert.h>

#include "plugin.h"

// ----------------------------------------------------------------------------
Particle* CreateParticle(const float pos[3], double zDist, float size,
                         BOOL align)
{
    Particle* newParticle = calloc(1, sizeof(Particle));

    newParticle->next = NULL;
    newParticle->pos[0] = pos[0];
    newParticle->pos[1] = pos[1];
    newParticle->pos[2] = pos[2];
    newParticle->zDist  = zDist;
    newParticle->align = align;
    newParticle->size = size;
    newParticle->colorDisplacement = 0;

    return newParticle;
}

// ----------------------------------------------------------------------------
Particle* InsertEnd(Particle* list, Particle* node)
{
    Particle *currNode;
    if (list == NULL) return NULL;

    currNode = list;
    
    while (currNode->next != NULL)
    {
        currNode = currNode->next;
    }

    currNode->next = node;
    node->next = NULL;

    return list;
}

// ----------------------------------------------------------------------------
Particle* InsertFront(Particle* list, Particle* node)
{
    node->next = list;
    return node;
}

// ----------------------------------------------------------------------------
Particle* InsertOrdered(Particle* list, Particle* node, int coordinate, 
                   BOOL ascending)
{
    Particle *currNode, *nextNode;

    if (list == NULL) return node;
    assert(coordinate < 3 && coordinate >= 0);

    currNode = NULL;
    nextNode = list;

    while (nextNode != NULL)
    {
        if ( ascending && nextNode->pos[coordinate] >= node->pos[coordinate] ||
            !ascending && nextNode->pos[coordinate] <= node->pos[coordinate])
        {
            break;
        }

        currNode = nextNode;
        nextNode = currNode->next;
    }

    if (currNode == NULL)
    {
        // insert at front
        node->next = list;
        list = node;
    }
    else
    {
        // insert at middle/end
        currNode->next = node;
        node->next = nextNode;
    }

    return list;
}

// ----------------------------------------------------------------------------
void Insert(Particle* afterNode, Particle* newNode)
{
    Particle* nextNode;
    
    if (afterNode == NULL) return;
    
    nextNode = afterNode->next;
    afterNode->next = newNode;
    newNode->next = nextNode;
}

// ----------------------------------------------------------------------------
int Iterate(Particle* list, IterateFunc iterateFunc, void* data)
{
    int count = 0;
    Particle *currNode, *nextNode;

    if (list == NULL) return 0;
        
    currNode = list;
    
    while (currNode != NULL)
    {        
        nextNode = currNode->next;
        if (iterateFunc != NULL) iterateFunc(currNode, count, data);
        
        currNode = nextNode;
        ++count;        
    }

    return count;
}

// ----------------------------------------------------------------------------
int ClearList(Particle* list)
{
    return Iterate(list, DeleteParticle, NULL);
}

// ----------------------------------------------------------------------------
void DeleteParticle(Particle* node, int id, void* data)
{
    free(node);
}

// ----------------------------------------------------------------------------
void PrintParticle(Particle* node, int id, void* data)
{
    if (node == NULL) return;
    printf("Particle %d: (%3.2f, %3.2f, %3.2f)\n", id, node->pos[0], 
        node->pos[1], node->pos[2]);
}

// ----------------------------------------------------------------------------
double Compare(Particle *a, Particle *b, BOOL ascending) {
    static double diff;
    diff = (a->zDist + a->colorDisplacement) - 
           (b->zDist + b->colorDisplacement);
    return ascending ? diff : -diff;
}

// --- Merge Sort for a linked list, thankfully taken from here: --------------
// --- http://www.chiark.greenend.org.uk/~sgtatham/algorithms/listsort.html ---
// ----------------------------------------------------------------------------
Particle* SortList(Particle *list, BOOL ascending) {
    Particle *p, *q, *e, *tail, *oldhead;
    int insize, nmerges, psize, qsize, i;

    if (!list) return NULL;

    insize = 1;

    while (1) {
        p = list;
        oldhead = list;                       /* only used for circular linkage */
        list = NULL;
        tail = NULL;

        nmerges = 0;  /* count number of merges we do in this pass */

        while (p) {
            nmerges++;  /* there exists a merge to be done */
            /* step `insize' places along from p */
            q = p;
            psize = 0;
            for (i = 0; i < insize; i++) {
                psize++;
                q = q->next;
                if (!q) break;
            }

            /* if q hasn't fallen off end, we have two lists to merge */
            qsize = insize;

            /* now we have two lists; merge them */
            while (psize > 0 || (qsize > 0 && q)) {

                /* decide whether next Particle of merge comes from p or q */
                if (psize == 0) {
                    /* p is empty; e must come from q. */
                    e = q; q = q->next; qsize--;                    
                } else if (qsize == 0 || !q) {
                    /* q is empty; e must come from p. */
                    e = p; p = p->next; psize--;                    
                } else if (Compare(p, q, ascending) <= 0) {
                    /* First Particle of p is lower (or same);
                     * e must come from p. */
                    e = p; p = p->next; psize--;                    
                } else {
                    /* First Particle of q is lower; e must come from q. */
                    e = q; q = q->next; qsize--;                    
                }

                /* add the next Particle to the merged list */
                if (tail) {
                    tail->next = e;
                } else {
                    list = e;
                }
                
                tail = e;
            }

            /* now p has stepped `insize' places along, and q has too */
            p = q;
        }
        
        tail->next = NULL;

        /* If we have done only one merge, we're finished. */
        if (nmerges <= 1)   /* allow for nmerges==0, the empty list case */
            return list;

        /* Otherwise repeat, merging lists twice the size */
        insize *= 2;
    }
}